一、題目介紹
今天要解的題目是LeetCode的House Robber

題目描述：
有一排房屋，每間房屋裡都有一定數量的金錢
我們希望偷到最多的金錢
但是有一個限制：不能偷相鄰的兩間房屋。
也就是說，如果偷了第i間房屋，就不能再偷第i - 1或第i + 1間。

例如：[2,7,9,3,1]
可以選擇：2 + 9 + 1 = 12
因此最大可以取得12

二、解題思路
這題最重要的問題是：走到第i間房屋時，我到底要不要偷這一間？

假設目前考慮第i間房屋，有兩種選擇

情況一：不偷第i間
那麼我們可以直接保留前一間的最佳結果dp[i - 1]

情況二：偷第i間
既然偷了第i間，就不能偷第i - 1間
因此可以取得dp[i - 2] + nums[i]

所以我們只需要比較這兩種情況dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

三、DP狀態定義
在這題中，我們可以定義dp[i]
代表：考慮前i間房屋時，可以偷到的最大金額

例如：nums = [2,7,9,3,1]

最後dp[5] = 12
所以答案就是12

四、狀態轉移過程
以[2,7,9,3,1]為例

第一間
只有一間房屋，因此直接偷dp[1] = 2

第二間
只能選擇兩間其中一間 max(2,7) = 7
所以dp[2] = 7

第三間
現在有兩種選擇

• 不偷第三間：dp[2] = 7
• 偷第三間：不能偷第二間，所以dp[1] + 9 = 2 + 9 = 11

取較大的dp[3] = max(7,11) = 11

第四間

• 不偷：dp[3] = 11
• 偷：dp[2] + 3 = 7 + 3 = 10

因此dp[4] = 11

第五間

• 不偷：dp[4] = 11
• 偷：dp[3] + 1 = 11 + 1 = 12

所以dp[5] = 12
最後答案就是12

五、Java實作

六、Python實作

七、空間最佳化
跟昨天的Climbing Stairs一樣，我們可以進一步觀察
計算dp[i]時，其實只會使用dp[i - 1]、dp[i - 2]
所以沒有必要保存完整的DP陣列

只需要使用兩個變數

• prev2
• prev1
  就可以完成計算

八、時間與空間複雜度
使用DP陣列
每間房屋只會被處理一次，因此
Time: O(n)
Space: O(n)

空間最佳化版本
同樣只需要走訪一次
Time: O(n)

但只使用固定數量的變數
Space: O(1)

九、Java與Python解法比較

十、實作結果
Leetcode測試結果：Accepted

十一、今日學習心得
今天的House Robber讓我對Dynamic Programming有更進一步的理解。

Day 17的Climbing Stairs是透過前兩個狀態推導目前的狀態，而今天的House Robber則需要先思考「目前這個選擇要不要做」。

在每一間房屋，我都需要比較兩種情況：
不偷目前房屋 → dp[i - 1]
偷目前房屋 → dp[i - 2] + nums[i]

再從兩者之中選擇較大的結果。

因此可以得到：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

這讓我發現，Dynamic Programming 並不是單純把結果一個一個存起來，而是需要先找出每個狀態代表什麼，以及目前的狀態如何從前面的狀態推導出來。

另外，今天也再次練習了空間最佳化。原本需要O(n)的DP陣列，因為每次只需要前兩個狀態，所以可以改成只使用幾個變數，將額外空間降低到O(1)。

今天最大的收穫是：面對DP問題時，可以先思考「目前有哪幾種選擇？」以及「每個選擇會依賴哪些之前的狀態？」